package interview.tree;

//非递归的中序遍历
public class InOrder
{
	// 定义一个函数:给一个node，让它返回下一个node
	public TreeNode next(TreeNode node)
	{
		// 处理特殊情况
		if (node == null)
		{
			return null;
		}

		if (node.getRight() != null)// 存在右子树
		{
			// 返回右子树的第一个结点
			return first(node.getRight());
		} else
		{// right是null，往上走
			// 当结点有父亲 并且 是父亲的右子树
			while (node.getParent() != null && node.getParent().getRight() == node)
			{
				node = node.getParent();// 一路往上走(往父亲走)
			}
			// node.getParent() == null(结点没有父亲) || node is left child of its
			// parent(结点是父亲的左子树)
			// 不走了
			return node.getParent();
		}
	}

	public TreeNode first(TreeNode node)// 求中序遍历中的第一个结点
	{
		// 判断特殊情况
		if (node == null)
		{
			return null;
		}

		// 一路往左走，走到走不下去为止
		TreeNode curNode = node;
		while (curNode.getLeft() != null)
		{
			curNode = curNode.getLeft();
		}
		return curNode;
	}

	public void traverse(TreeNode root)
	{
		// 从树的第一个结点开始
		for (TreeNode node = first(root); node != null; node = next(node))
		{
			System.out.print(node.getValue());
		}
		System.out.println();
	}

	public static void main(String[] args)
	{
		TreeCreator creator = new TreeCreator();
		InOrder inOrder = new InOrder();

		TreeNode sampleTree = creator.createSampleTree();
		inOrder.traverse(sampleTree);

		// 边界值测试
		inOrder.traverse(creator.createTree("", ""));// 空树
		inOrder.traverse(creator.createTree("A", "A"));// 单结点
		inOrder.traverse(creator.createTree("AB", "BA"));// 把树根放到最后
		// 提高覆盖率
		inOrder.traverse(creator.createTree("ABCD", "DCBA"));// 只有左子树
		inOrder.traverse(creator.createTree("ABCD", "ABCD"));// 只有右子树
	}

}
